class Solution {
public:
	vector<int> findSubstring(string s, vector<string>& words) {
		vector<int> ret;
		unordered_map<string, int> hash2; // 保存 words ⾥⾯所有单词的频次
		for (auto& e : words) 
        {
            hash2[e]++;
        }
		int len = words[0].size(), m = words.size();
		for (int i = 0; i < len; i++) // 执⾏ len 次
		{
            int left = i, right = i, count = 0;
			unordered_map<string, int> hash1; // 维护窗⼝内单词的频次
			while (right + len <= s.size())
			{
				string in = s.substr(right, len); // 进窗⼝ + 维护 count
				hash1[in]++;
				if (hash2.count(in) && hash1[in] <= hash2[in])
                {
                    count++;
                }
				if (right - left + 1 > len * m) // 判断
				{
					// 出窗⼝ + 维护 count
					string out = s.substr(left, len);
					if (hash2.count(out) && hash1[out] <= hash2[out])
                    {
                        count--;
                    }
					hash1[out]--;
					left += len;
				}
				if (count == m) // 更新结果
                {
                    ret.push_back(left);
                }
                right += len;
			}
		}
		return ret;
	}
};